package 动态规划.背包问题01;

/**
 * 题意概要：有 n 个物品和一个容量为 W 的背包，每个物品有重量 w_{i} 和价值 v_{i} 两种属性，
 * 要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
 */
public class Solution {

    public int backPackII(int m, int[] a, int[] v) {
        // write your code here
        // dp[i][j]   -> 装前面i个物品的时候, 容量为j的最大价值
        // dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight] + value)
        int n = a.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= a[i - 1]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - a[i - 1]] + v[i - 1]);
            }
        }
        return dp[n][m];
    }

    // 利用一维数组来解决
    public int backPackIII(int m, int[] A, int[] V) {
        // dp[i] 代表容量为i的背包所能获得的最大价值
        int row = A.length;
        if (m == 0) return 0;
        int[] dp = new int[m + 1];
        for (int i = 0; i < row; i++) {
            for (int j = m; j >= A[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
            }
        }
        return dp[m];
    }

}
